package genetic;
// Alex Umrysh
// SCSC599
// 2-21-2011
import java.util.Random;
import java.util.Scanner;


public class main
{
	static Random rand = new Random();

	public static void main(String[] args)
	{
		int lengthOfStr = 0;
		Scanner scan = new Scanner(System.in);
		String target = "";

		if (args.length == 0)
		{
			System.out.print("Please input a target string: ");
			target = scan.nextLine();
		}
		else
		{
			target = args[0];
		}
		lengthOfStr = target.length();

		int popSize = 300;
		int generation = 0;

		// array of strings will be the population
		String[] population = new String[popSize];

		// first random population
		for (int i = 0; i < popSize; i++)
		{
			// random string for population element i
			//population[i] = RandomStringUtils.randomAscii(lengthOfStr);
		}

		boolean found = false;
		// found = true;
		while (!found)
		{
			// main genetic algo. loop
			System.out.print("Generation: " + generation + " | ");

			// create children array and populate via
			// mating/crossover/combination
			String[] children = new String[popSize];
			String fittest = "";
			int thisrating = 999999999; // just some really poor rating
			int rating = 0;
			for (int i = 0; i < popSize && !found; i++)
			{
				rating = fitness(target, population[i]);
				// check the genomes for a win
				if (rating == 0)
				{
					System.out.println(population[i] + " | 0");
					System.out.println("Found match, pop num: " + i);
					found = true;
				}
				if (rating < thisrating)
				{
					fittest = population[i];
				}

				// build the next generation
				// using tournament selection to select two parents from 4
				// random
				String[] mated = tournament(target, population[rand.nextInt(popSize)],
						population[rand.nextInt(popSize)], population[rand
								.nextInt(popSize)], population[rand
								.nextInt(popSize)]);

				// this randomly selects one of two children created by the
				// tournament mating
				if (rand.nextBoolean())
				{
					children[i] = mated[0];
				}
				else
				{
					children[i] = mated[1];
				}

			}

			// children array has been made, now replace the parents with the
			// children and do again
			for (int i = 0; i < popSize; i++)
			{
				population[i] = children[i];
			}

			// print out the fittest and it's rating
			if (!found)
			{
				System.out.println(fittest + " | " + rating);
			}

			// increment generation
			generation++;
		}

		// finished the genetic algo
		System.out.println("Found in " + generation + " generations.");
		
		
		
//	//	Interpreter interp = new Interpreter();
//		while (true)
//		{
//			try
//			{
//				interp.eval(scan.nextLine());
//			}
//			catch (EvalError e)
//			{
//				// TODO Auto-generated catch block
//				System.out.println("-----BEANSHELL-----");
//				e.printStackTrace();
//				System.out.println("-----BEANSHELL-----");
//			}
//		}
	}

	/**
	 * fitness
	 * 
	 * @param target
	 *            target string
	 * @param s
	 *            input string
	 * @return the number of characters that are wrong
	 */
	public static int fitness(String target, String s)
	{
		int retval = 0;
		// Return the number of wrong chars
		for (int i = 0; i < target.length(); i++)
		{
			if (target.charAt(i) != s.charAt(i))
			{
				// retval += Math.abs((((int) target.charAt(i)) - ((int)
				// s.charAt(i))));
				retval++;
			}
		}
		return retval;
	}

	/**
	 * mutation
	 * 
	 * @param s
	 * @return a possibly mutated string based on the input string s changes
	 *         random characters sometimes, similar to natural mutation from
	 *         radiation
	 */
	public static String mutation(String s)
	{
		int lengthOfStr = s.length();
		// expresses random deviations in the population
		String retstr = s;
		while (rand.nextBoolean())
		{
			// string construction
			int index = rand.nextInt(lengthOfStr + 1);

			// split the string at this index and add a random character at the
			// index
			if (index == 0)
			{
//				retstr = RandomStringUtils.randomAscii(1) + s.substring(1);
			}
			else if (index == lengthOfStr)
			{
//				retstr = s.substring(0, lengthOfStr - 1)
//						+ RandomStringUtils.randomAscii(1);
			}
			else
			{
//				retstr = s.substring(0, index)
//						+ RandomStringUtils.randomAscii(1)
//						+ s.substring(index + 1, lengthOfStr);
			}
		}
		return retstr;
	}

	/**
	 * combination
	 * 
	 * @param S
	 *            parent 1
	 * @param T
	 *            parent 2
	 * @return the result of mating parent 1 with parent 2
	 */
	public static String crossover(String S, String T)
	{
		int lengthOfStr = S.length();
		if (S.length() > 1 && T.length() > 1)
		{
			int index = rand.nextInt((lengthOfStr / 3) + (lengthOfStr / 2));
			String retstr = S;
			// do a recombination of the two strings from some random point
			retstr = S.substring(0, index) + T.substring(index, lengthOfStr);
			return retstr;
		}
		else
		{
			return T;
		}
	}

	/**
	 * tournament selection
	 * 
	 * @param s1
	 * @param s2
	 * @param s3
	 * @param s4
	 * @return the mating of the highest fitness parents
	 */
	public static String[] tournament(String target, String s1, String s2, String s3, String s4)
	{
		String retstr = "";
		String retstr2 = "";
		String[] retarr = new String[2];

		// initialize parent1 and parent2
		String p1 = s1;
		String p2 = s3;

		// possibly change parent1,2
		if (fitness(target, s1) > fitness(target, s2))
		{
			p1 = s2;
		}
		if (fitness(target, s3) > fitness(target, s4))
		{
			p2 = s4;
		}

		// mate the two parents both ways
		retstr = crossover(p1, p2);
		retstr2 = crossover(p2, p1);
		// random mutation
		retstr = mutation(retstr);
		retstr2 = mutation(retstr2);

		// stuffing the two results into the return array
		retarr[0] = retstr;
		retarr[1] = retstr2;
		return retarr;
	}

	public static void evolve(String target)
	{
		int lengthOfStr = target.length();

		int popSize = 300;
		int generation = 0;

		// array of strings will be the population
		String[] population = new String[popSize];

		// first random population
		for (int i = 0; i < popSize; i++)
		{
			// random string for population element i
//			population[i] = RandomStringUtils.randomAscii(lengthOfStr);
		}

		boolean found = false;
		// found = true;
		while (!found)
		{
			// main genetic algo. loop
			System.out.print("Generation: " + generation + " | ");

			// create children array and populate via
			// mating/crossover/combination
			String[] children = new String[popSize];
			String fittest = "";
			int thisrating = 999999999; // just some really poor rating
			int rating = 0;
			for (int i = 0; i < popSize && !found; i++)
			{
				rating = fitness(target, population[i]);
				// check the genomes for a win
				if (rating == 0)
				{
					System.out.println(population[i] + " | 0");
					System.out.println("Found match, pop num: " + i);
					found = true;
				}
				if (rating < thisrating)
				{
					fittest = population[i];
				}

				// build the next generation
				// using tournament selection to select two parents from 4
				// random
				String[] mated = tournament(target, population[rand.nextInt(popSize)],
						population[rand.nextInt(popSize)], population[rand
								.nextInt(popSize)], population[rand
								.nextInt(popSize)]);

				// this randomly selects one of two children created by the
				// tournament mating
				if (rand.nextBoolean())
				{
					children[i] = mated[0];
				}
				else
				{
					children[i] = mated[1];
				}

			}

			// children array has been made, now replace the parents with the
			// children and do again
			for (int i = 0; i < popSize; i++)
			{
				population[i] = children[i];
			}

			// print out the fittest and it's rating
			if (!found)
			{
				System.out.println(fittest + " | " + rating);
			}

			// increment generation
			generation++;
		}

		// finished the genetic algo
		System.out.println("Found in " + generation + " generations.");
	}
}
